package com.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class InsertSort {
    public static void main(String[] args) {
        //int [] arr = {101,34,119,1};

        //测试一下冒泡的速度O(n^2),给八万个数据，测试
        //创建要给80000个的随机数组
        int[] arr =new int[8];
        for (int i = 0; i < 8; i++) {
            //生成一个[0，80000]数
            arr[i] = (int)(Math.random()*80000);
        }

        System.out.println("排序前");
        //测试排序前的时间
        Date date2 = new Date();
        //输出时间格式
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyy-mm-dd HH:mm:ss");
        //有了这些我们可以拿到一个字符串
        String deta2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间"+deta2);

        insertSort(arr);

        Date date3 = new Date();
        //有了这些我们可以拿到一个字符串
        String deta3 = simpleDateFormat.format(date3);
        System.out.println("排序后的时间"+deta3);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] arr){

        //使用for循环来把代码简化
        for (int i = 1; i <arr.length ; i++) {
            //实用逐步推到的方法来讲解，便于理解
            //第一轮 {101，34，119，1}； =》 {34，101，119，1}

            //定义待插入的数
            int insertVal = arr[i];
            //即arr[1]的前面这个数的下标
            int insertIndex = i-1;

            //给inserrtVal 找到插入的位置
            //说明
            //1.insertIndex >= 0 保证在给insertVal 找插入位置，不越界
            //2.insertIndex < arr[insertIndex]待插入的数，还没有找到插入的位置
            //3.就需要将arr[insertIndex] 后后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex]; //arr [insertIndex]
                insertIndex--;
            }
            //当退出while循环时，说明插入的位置找到，insertIndex + 1；

            //这里我们判断下是否需要赋值
            if (insertIndex +1 != i) {
                arr[insertIndex + 1] = insertVal;
            }

            //System.out.println("第"+i+"轮插入后");
           // System.out.println(Arrays.toString(arr));
        }

      /*  //实用逐步推到的方法来讲解，便于理解
        //第一轮 {101，34，119，1}； =》 {34，101，119，1}

        //定义待插入的数
        int insertVal = arr[1];
        //即arr[1]的前面这个数的下标
        int insertIndex = 1-1;

        //给inserrtVal 找到插入的位置
        //说明
        //1.insertIndex >= 0 保证在给insertVal 找插入位置，不越界
        //2.insertIndex < arr[insertIndex]待插入的数，还没有找到插入的位置
        //3.就需要将arr[insertIndex] 后后移
        while (insertIndex >= 0 && insertVal < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //arr [insertIndex]
            insertIndex--;
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1；

        arr[insertIndex + 1] = insertVal;
        System.out.println("第一轮插入后");
        System.out.println(Arrays.toString(arr));

        //第二轮
        //定义待插入的数
         insertVal = arr[2];
        //即arr[1]的前面这个数的下标
         insertIndex = 2-1;

         //给inserrtVal 找到插入的位置
        //说明
        //1.insertIndex >= 0 保证在给insertVal 找插入位置，不越界
        //2.insertIndex < arr[insertIndex]待插入的数，还没有找到插入的位置
        //3.就需要将arr[insertIndex] 后后移
        while (insertIndex >= 0 && insertVal < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //arr [insertIndex]
            insertIndex--;
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1；

        arr[insertIndex + 1] = insertVal;
        System.out.println("第二轮插入后");
        System.out.println(Arrays.toString(arr));


        //第三轮
        //定义待插入的数
        insertVal = arr[3];
        //即arr[1]的前面这个数的下标
        insertIndex = 3-1;

        //给inserrtVal 找到插入的位置
        //说明
        //1.insertIndex >= 0 保证在给insertVal 找插入位置，不越界
        //2.insertIndex < arr[insertIndex]待插入的数，还没有找到插入的位置
        //3.就需要将arr[insertIndex] 后后移
        while (insertIndex >= 0 && insertVal < arr[insertIndex]){
            arr[insertIndex + 1] = arr[insertIndex]; //arr [insertIndex]
            insertIndex--;
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1；

        arr[insertIndex + 1] = insertVal;
        System.out.println("第三轮插入后");
        System.out.println(Arrays.toString(arr));*/
    }
}
